"""
BFS模板

例子：
输出如下图的每个连通块大小
[
    [0, 1, 0, 1, 0]
    [0, 1, 0, 0, 1]
    [0, 0, 0, 0, 1]
    [0, 1, 1, 0, 1]
    [0, 1, 0, 0, 1]
    [0, 0, 1, 1, 1]
]
"""

import collections


class Solution:
    def sizeofBlock(self, grid):
        ROW = len(grid)
        COL = len(grid[0])
        
        visited = [ [False]*COL for _ in range(ROW) ]
        
        def neighbor(r, c):
            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if 0<=nr<ROW and 0<=nc<COL:
                    yield nr, nc
        
        def BFS(r, c):
            nonlocal visited
            visited[r][c] = True
            queue = collections.deque()
            queue.append( (r, c) )
            land = 1
            
            while queue:
                r, c = queue.popleft()
                
                for nr, nc in neighbor(r, c):
                    if grid[nr][nc] == 1 and visited[nr][nc] == False:
                        visited[nr][nc] = True
                        """
                        **** 注意此处关于访问标志位的位置 ****
                        需要在遍历四周邻近点时（循环内），进行设置
                        否则会造成邻近点的重复添加（增加耗时）

                        会不会造成死循环？
                        当前这个情况下不会，因为节点在队列中会被弹出，最终会被设为已经访问，只是多了几次重复
                        其他条件下，可能造成死循环
                        """
                        land += 1
                        queue.append( (nr, nc) )
            
            return land 
        

        for r in range(ROW):
            for c in range(COL):
                if visited[r][c] == False and grid[r][c] == 1:
                    print(BFS(r, c))


grid = \
[
    [0, 1, 0, 1, 0],
    [0, 1, 0, 0, 1],
    [0, 0, 0, 0, 1],
    [0, 1, 1, 0, 1],
    [0, 1, 0, 0, 1],
    [0, 0, 1, 1, 1]
]

S = Solution()
S.sizeofBlock(grid)
